package base.internal;

import java.util.LinkedList;
import java.util.List;

import util.StringTool;

import base.Sort;

public class SeqMergeSort implements Sort {

	@Override
	public String[] sort(List<String> lines, String separator) {

		int size = lines.size();
		String[] g = new String[size];
		g = lines.toArray(g);
		String[] s;
		for (int i = 0; i < size; i++) {
			s = g[i].split(separator);
			sort(s, 0, s.length - 1);
			g[i] = StringTool.arrayToString(s, separator);
		}

		sort(g, 0, size - 1);

		return g;
	}

	private void sort(String[] line, int begin, int end) {
		if (begin == end)
			return;

		int middle = (begin + end) / 2;

		sort(line, begin, middle);
		sort(line, middle + 1, end);
		int aux_size = end - begin + 1;
		String[] aux = new String[aux_size];
		int left = begin;
		int right = middle + 1;

		for (int i = 0; i < aux_size; i++) {
			if (right > end	|| (left <= middle && (line[left].compareTo(line[right]) <= 0))) {
				aux[i] = line[left];
				left++;
			} else {
				aux[i] = line[right];
				right++;
			}
		}
		for (int i = 0; i < aux_size; i++)
			line[begin + i] = aux[i];
	}

	public static void main(String[] args) {
		// start time // computation time: 47.265
		//long startTime = System.currentTimeMillis();

		List<String> s = new LinkedList<String>();
		s.add("amor");
		for(int i = 0; i < 500; i++){
			s.add(s.get(s.size()-1) + " " + System.currentTimeMillis());
		}
		
		// start time
		long startTime = System.currentTimeMillis();
		// end time
		new SeqMergeSort().sort(s, " ");
		long endTime = System.currentTimeMillis();
		float time = (endTime - startTime) / 1000.0f;
		System.out.println("computation time: " + time);

		//System.out.println(StringTool.arrayToString(new ConcurrentMergeSort().sort(s, " "), "\n"));
	}

}
